package com.demo.datastructure.tree;

/**
 * @description: 二叉查找树
 * @author: ljr
 * @time: 2021/5/25 21:36
 */
public class BinarySearchTree{

    private Node tree;

    public Node find(int data){
        Node p = tree;
        while(p != null){
            if(p.data == data){
                return p;
            }

            if(data < p.data){
                p = p.left;
            }else{
                p = p.right;
            }
        }
        return null;
    }

    public Node insertNode(int data){
        Node newNode = new Node(data);
        Node p = tree;
        while(p != null){
            if(p.data > data){
                if(p.left == null){
                    p.left = newNode;
                    return newNode;
                }
                p = p.left;
            }else{
               if(p.right == null){
                    p.right = newNode;
                    return newNode;
                }
                p = p.right;
            }
        }
        tree = newNode;
        return newNode;
    }

    public void delete(int data){
        Node p = tree;
        Node pp = null;
        while(p != null && p.data != data){
            pp = p;
            if(data < p.data) p = p.left;
            else p = p.right;
        }

        if(p == null){
            return;
        }

        if(p.left != null && p.right != null){
            Node minp = p.right;
            Node minpp = p;
            while(minp.left != null){}{
                minpp = minp;
                minp = minp.left;
            }
            p.data = minp.data; // 将minP的数据替换到p中
            p = minp;
            pp = minpp;
        }

        Node child;
        if(p.left != null) child = p.left;
        else if(p.right != null) child = p.right;
        else child = null;

        if(pp == null){
            tree = child;
        }else if(pp.left == p){
            pp.left = child;
        }else{
            pp.right =child;
        }
    }


    public Integer min(){
        return min(tree);
    }

    private Integer min(Node node){
        if(node == null){ return  null;}
        Node current = node;
        while (current.left != null){
            current = current.left;
        }
        return current.data;
    }

    public Integer max(){
        return max(tree);
    }

    private Integer max(Node node){
        if(node == null){ return  null;}
        Node current = node;
        while (current.right != null){
            current = current.right;
        }
        return current.data;
    }




    public void delete2(int data){
        Node current = tree;
        Node p = null;
        while(current != null && current.data != data){
            p = current;
            if(current.data < data) current = current.left;
            else current = current.right;
        }

        if(current == null) return;

        Node min = current;
        Node minP = p;
        if(min.left != null && min.right != null){
             minP = min;
             min = min.right;
             while(min.left != null){
                 minP = min;
                 min = min.left;
             }
             current.data = min.data;
        }

        Node child = null;
        if(min.left != null){
            child = min.left;
        }else if(min.right != null){
            child = min.right;
        }

        if(minP == null){
            tree = child;
        }else if(minP.left == min){
            p.left = child;
        }else if(minP.right == min){
            p.right = child;
        }
    }

    public int maxDepth(Node root) {
        if(root == null){ return 0;}
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }


     private static class Node{
        private Integer data;

        private Node left;

        private Node right;

        public Node(int data) {
            this.data = data;
        }

        public Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insertNode(33);
        tree.insertNode(17);
        tree.insertNode(50);
        tree.insertNode(13);
        tree.insertNode(18);
        tree.insertNode(34);
        tree.insertNode(58);
        tree.insertNode(16);
        tree.insertNode(25);
        tree.insertNode(51);
        tree.insertNode(66);
        tree.insertNode(19);
        tree.insertNode(27);
        System.out.println(tree.max());
        System.out.println(tree.min());
    }

}
